package gold.digger;

import gold.utils.InputUtil;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC324 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public void wiggleSort(int[] arr) {
            int[] copy = new int[arr.length];
            Arrays.sort(arr);
            for (int i = 0; i < (arr.length + 1) / 2; i++) {
                if (2 * i + 1 < arr.length) copy[2 * i + 1] = arr[arr.length - 1 - i];
                copy[2 * i] = arr[(arr.length - 1) / 2 - i];
            }

            for (int i = 0; i < arr.length; i++) {
                arr[i] = copy[i];
            }
        }
    }

    /*
     * @param 此解法为别人算法
     * 此中参考快排寻找中位数的解法，值得多多学习
     * @return:
     */
    class Solution_FindMiddleNum {
        public void wiggleSort(int[] nums) {
            if (nums == null || nums.length == 0) return;
            int length = nums.length, mid = nums.length / 2;
            if (length % 2 == 0) mid -= 1;
            quickSelect(nums, 0, length - 1, mid);

            int i = 0, j = 0, k = length - 1;
            //亦为荷兰国旗的核心代码
            while (j < k) {
                if (nums[j] > nums[mid]) {
                    swap(nums, j, k);
                    k--;
                } else if (nums[j] < nums[mid]) {
                    swap(nums, i, j);
                    i++;
                    j++;
                } else {
                    j++;
                }
            }
            //亦为荷兰国旗的核心代码
            int[] tmp = new int[length];
            for (i = 0; i < length; i++) {
                tmp[i] = nums[i];
            }
            i = mid;
            j = length - 1;
            k = 0;
            boolean flag = true;
            while (k < length) {
                if (flag) {
                    nums[k++] = tmp[i--];
                    flag = false;
                } else {
                    nums[k++] = tmp[j--];
                    flag = true;
                }
            }
        }

        private void quickSelect(int[] nums, int start, int end, int mid) {
            int ind = partition(nums, start, end);
            if (mid == ind) return;
            else if (mid > ind) {
                quickSelect(nums, ind + 1, end, mid);
            } else {
                quickSelect(nums, start, ind - 1, mid);
            }
        }

        private int partition(int[] nums, int start, int end) {
            int soilder = start, left = start + 1;
            while (left <= end) {
                while (left <= end && nums[left] <= nums[soilder]) {
                    left++;
                }
                while (left <= end && nums[end] > nums[soilder]) {
                    end--;
                }
                if (left > end) break;
                swap(nums, left, end);
                left++;
                end--;
            }
            swap(nums, left - 1, soilder);
            return left - 1;
        }

        private void swap(int[] nums, int num1, int num2) {
            int tmp = nums[num1];
            nums[num1] = nums[num2];
            nums[num2] = tmp;
        }
    }


    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1, 3, 2, 2, 3, 1]");
        solution.wiggleSort(arr);
    }

    public static void main(String[] args) throws Exception {
        LC324 an = new LC324();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
